
from functools import cache

class Solution:

    def mincostTickets(self, days, costs):

        # 递归的做法
        # last_day = days[-1]

        # # 避免重复
        # days = set(days)

        # @cache
        # def dfs(i):
        #     if i <= 0 :
        #         return 0
        #     # 有些时间是不旅行的
        #     if i not in days:

        #         return dfs(i - 1)
            
        #     return min(dfs(i - 1) + costs[0], dfs(i - 7) + costs[1], dfs(i - 30) + costs[2])
        

        # return dfs(last_day)

        # 动态规划的做法

        last_day = days[-1]

        days = set(days)

        dp = [0] * (last_day + 1)

        for i in range(1, last_day + 1):

            if i not in days:

                dp[i] = dp[i - 1]
            
            else:

                dp[i] = min(dp[i - 1] + costs[0],
                           dp[max(i - 7, 0)] + costs[1],
                           dp[max(i - 30, 0)] + costs[2])
            
        
        return dp[-1]
    










